package com.banyiyi.simple.pattern.algroithm;

import java.util.Arrays;
import java.util.PrimitiveIterator;

/**
 * @ClassName RadixSort
 * @Description 基数排序
 * @Author yangwm
 * @Date 2023/2/17 11:37
 * @Version 1.0
 */
public class RadixSort {

    public static void main(String[] args) {
        // 首先考虑 一个数字如何获取 个位 十位 百位 千位 ...

        int[] arr = new int[]{53, 3, 542, 748, 14, 214, 154, 63, 616};
        //                     0  1   2   3    4    5    6    7    8
        /**
         * 2    542
         * 3    53 3 63
         * 4    14 124 214
         * 6    616
         * 8    748
         */
        radixSort(arr);
        PrimitiveIterator.OfInt iterator = Arrays.stream(arr).iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

    }

    // 求最大值（来计算最大循环次数）
    private static int getMaxNumber(int[] arr){
        if(arr.length < 1) return 0;
        int max = arr[0];
        for (int i : arr) {
            max = Math.max(max,i);
        }
        return max;
    }
    // 对数组进行指定“位”置的计数排序
    private static void sort(int[] arr, int k){
        // 定义排序的桶
        int[] bucket = new int[10];
        // 定义临时存储值的数组
        int[] temp = new int[arr.length];

        // 循环添加到对应桶
        for (int i = 0; i < arr.length; i++) {
            bucket[(arr[i]/k)%10]++;
        }
        // 找到桶中排序数对应的元素位置
        // 将桶中元素进行从小到大累加，每个桶的数字代表的是在新数组中的元素最大位置
        for (int i = 1; i < 10; i++) {
            bucket[i] += bucket[i-1];
        }
        // 将对应的元素根据排好的下标进行插入到新数组，形成初次排序
        for (int i = arr.length - 1; i >= 0; i--) {
            temp[bucket[(arr[i]/k)%10] - 1] = arr[i];
            bucket[(arr[i]/k)%10]--;
        }

        // 数组重新赋值
        System.arraycopy(temp,0,arr,0,temp.length);

    }
    // 循环
    private static void radixSort(int[] arr){
        int k ;
        int max = getMaxNumber(arr);
        for(k = 1; max/k > 0; k*=10){
            sort(arr,k);
        }
    }
}
